This invention relates to random access memory architectures, both classical and quantum. More particularly, it deals with apparatus and methods for reducing the number of physical interactions needed to address a random memory cell in an array of cells. A fundamental ability of any computing device is the capacity to store information in an array of memory cells. The most flexible architecture for memory arrays is random access memory, or RAM, in which any memory cell can be addressed at will. A RAM is composed of a memory array, an input register (called an “index register”), and a data register. Each cell of the array is associated with a unique numerical address. In a read operation, when the index register is initialized with the address of a memory cell, the content of the cell is returned at the data register (an operation called “decoding”). This can be expressed as:Input (index register)=j→Output=Dj  (1)
where Dj is the content of the jth memory cell. A “write” operation is entirely analogous: the contents of the data register are stored in the memory cell indexed by the index register. For clarity, in the following discussion only the “read” operation will be described with the understanding that the “write” operation is analogous.
Conventional address decoders use binary trees of decoding switches that allow the bits of the address to pick out a particular wire. For a two-dimensional memory array, the number of decoding switches that are activated in the course of a single memory access is on the order of the square root of the number of memory slots: O(2(n/2)) decoding switches are activated to pick out the addressing wire on one side of the array, and another O(2(n/2)) decoding switches are activated to pick out the addressing wire on the other side of the array.
In particular, if the index register contains the desired address in binary form, each bit of the register can be interpreted as a direction for the data signal to take at a bifurcation of a binary tree. Since the n bits encode the directions to take at n bifurcations, then 2n different paths can be described this way.
A realization 100 of the conventional addressing procedure is shown in FIG. 1. Suppose that the N memory cells are placed at the end of a bifurcation graph, composed by the n levels, such as the one depicted in FIG. 1, where the first level is composed by the switch 104, the second level by 105 and 106, and so on. The value of the jth bit in the index register can be interpreted as the route to follow when one has reached a node in the jth level of the graph. If the value is 0, the upper path must be followed 102; if it is 1, the lower path must be followed 103 (for example, an index register 010 . . . is interpreted as “up” at the first level, “down” at the second level, “up” at the third, etc.). Each of the N possible values of the index register thus indicates a unique route that crosses the whole graph and reaches one of the memory cells 107. Therefore, a d-dimensional RAM consists of d such graphs, each addressing one side of a N1/d×N1/d× . . . array. This is sometimes called a “fanout” RAM addressing scheme, since each index bit “fans out” to control several decoding switches placed on different nodes of the binary decoder tree.
Fanout schemes are commonly implemented in RAM chips (see, for example, T. N. Blalock and R. C. Jaeger, Microelectronic circuit design, Cambridge Univ. Press, Cambridge, 2000) by translating them into electronic circuits where the switches of the binary tree are replaced by pairs of transistors as illustrated in FIG. 2. This prior art electronic implementation requires placing one transistor in each of the two paths following each node in the graph. All the transistors in the upper paths (for example, paths 209, 211 and 212) are activated if the corresponding index bit is zero and all the transistors in the lower paths (for example, paths 210, 213 and 214) are activated if the corresponding index bit is one. For every state of the index register, only one out of the 2n possible paths has all the switches in a “conducting” state. Therefore, a signal will follow the path to the memory cell that the index register is addressing.
Since each index register bit controls all the transistors in one of the graph levels, an exponential number of transistors must be activated at each memory call to route the signals through the graph and this entails an energy cost exponentially larger than the cost of a single transistor activation. The main drawback of the fanout architecture is that it requires simultaneous control over all the 2n−1 nodes of the binary tree even though only n nodes directly participate to the addressing of a given memory cell (these are the switches which lie along the path to the addressed memory cell).
The number of active transistors can be reduced to O(n) by modifying the aforementioned arrangement. In particular, in FIG. 3, the fanout RAM architecture is modified to attain a circuit where, at each level of the binary tree, only two transistors are activated (for example, transistors 304 and 305 at the third level of the graph), and where at the final stage only a single transistor 309 is activated to open up the unique path to the desired memory slot. In total only 2n+1 transistors are activated for every memory call.
A quantum computer is a device that stores bits of information on individual quanta: one atom, one bit. Quantum bits (called “qubits”), have a counterintuitive feature that they can exist in a state of 0 and 1 simultaneously, a phenomenon called “quantum superposition”. Quantum computers exploit quantum superposition to perform many computations simultaneously, in quantum parallel, with the qubit in the quantum computer existing in superpositions of 0 and 1 during the course of the computation. This ability of quantum computers to use quantum superpositions makes them in principle more powerful than conventional digital computers.
Just as a RAM forms an essential component of classical computers, quantum random access memory or qRAM will make up an essential component of quantum computers, should large quantum computers eventually be built. It has the same three basic components as the RAM, but the index and data registers are composed of qubits (quantum bits) instead of bits. The memory array can be either quantum or classical, depending on the qRAM's usage. The qRAM can then perform memory accesses in coherent quantum superposition (as described in M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information, Cambridge Univ. Pr., Cambridge, 2000). If a quantum computer needs to access a superposition of memory cells, the index register a must contain a superposition of addresses
      ∑    j    ⁢            ψ      j        ⁢                          j        〉            a      and the qRAM will return a superposition of data in a data register d, correlated with the index register:
                              ∑          j                ⁢                              ψ            j                    ⁢                                                                    j                〉                            a                        ⁢                          ⟶              qRAM                        ⁢                                          ∑                j                            ⁢                                                ψ                  j                                ⁢                                                                          j                    〉                                    a                                ⁢                                                                                                D                      j                                        〉                                    d                                                                                        (        2        )            
where Dj is the content of the jth memory cell.
It is possible to directly translate the addressing arrangements used for classical RAMs into the quantum realm (for example, see M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, 2000). In these translations, the n qubits of the index register coherently control n quantum control lines, each of which acts coherently on an entire level of the bifurcation graph. At each branch of the bifurcation graph, a 0 in the index register for that level shunts signals along the upper paths, and a 1 in the index register shunts signals along the lower paths. Each binary address in the index register is correlated with a set of switches that pick out the unique path through the graph associated with that address. A coherent superposition of addresses is coherently correlated, i.e. entangled, with a set of switches that pick out a superposition of paths through the graph.
To complete a quantum memory read access (the “write” operation is completely analogous), a quantum “bus” is injected at the root node and follows the superposition of paths through the graph. Then the internal state of the bus is changed according to the quantum information in the memory slot at the end of the paths (for example, via a controlled-NOT transformation that correlates the bus and the memory). Finally, in order to decorrelate the bus position from the index register, the bus returns to the root node by the same path. Like a quantum particle, the bus must be capable of traveling down a coherent superposition of paths. Although not impossible, such a qRAM scheme is highly demanding in practice for any reasonably-sized memory. In fact, to query a superposition of memory cells, the index register qubits are in general entangled with O(N) switches or quantum gates (or, equivalently, they must control two-body interactions over exponentially large regions of space), that is, a state of the form:
                              ∑          j                ⁢                              ψ            j                    ⁢                                                                                                          j                    0                                    ⁢                                      j                    1                                    ⁢                  …                  ⁢                                                                          ⁢                                      j                                          n                      -                      1                                                                      〉                            a                        ⊗                                                                            j                  0                                〉                                            s                0                                              ⁢                                                                  j                1                            〉                                      s              1                                      ⊗              2                                ⁢          …          ⁢                                          ⁢                                                                  j                                  n                  -                  1                                            〉                                      s                              n                -                1                                                    ⊗                              2                                  n                  -                  1                                                                                                    
where jk is the kth bit of the index register, and sk is the state of the 2k switches controlled by the kth bit of the index register. Such a gigantic superposition is highly susceptible to decoherence and requires costly quantum error correction whenever the error rate is bigger than 2−n. In fact, if a single gate out of the N=2n gates in the array is decohered, then the fidelity of the state in average is reduced by a factor of two, and if at least one gate in each of the k lines is decohered, the fidelity in average is reduced by 2−k.
The possibility of efficiently implementing a qRAM would yield significant advantages in many fields. For example, it would give an exponential speedup for pattern recognition algorithms (G. Schaller and R. Schutzhold, Physical Review A, 74:012303, 2006; R. Schutzhold. Physical Review A, 67:062311, 2003; C. A. Trugenberger. Physical Review Letters, 89:277903, 2002), period finding, discrete logarithm and quantum Fourier transform algorithms over classical data. Moreover, qRAMs are required for the implementation of various algorithms, such as quantum searching on a classical database (M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, 2000), collision finding (P. Hø yer, G. Brassard and A. Tapp. ACM SIGACT News (Cryptology Column), 28:14,1997), element-distinctness in the classical and quantum settings (A. Ambainis. Proceedings 45th IEEE FOCS'04, preprint quant-ph/0311001, 4393:598, 2004; A. W. Harrow, A. M. Childs and P. Wocjan. Proceedings 24th Symposium on Theoretical Aspects of Computer Science (STACS 2007), Lecture Notes in Computer Science, 4393:598, 2007), and the quantum algorithm for the evaluation of general NAND trees (A. M. Childs et al. Proceedings 48th IEEE Symposium on Foundations of Computer Science (FOCS'07), quant-ph/0703015, 2008). Finally, qRAMs permit the introduction of new quantum computation primitives, such as quantum cryptographic database searches (S. Lloyd, V. Giovannetti and L. Maccone. Physical Review Letters, 100, 230502, 2008) or the coherent routing of signals through a quantum network of quantum computers (S. Lloyd, V. Giovannetti and L. Maccone. unpublished, 2008).